import java.util.ArrayList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 */
class Solution {
    StringBuilder path;
    List<String> ret;
    String[] hash;
    public List<String> letterCombinations(String digits) {
        //映射关系
        hash = new String[10];
        hash[2] = "abc";
        hash[3] = "def";
        hash[4] = "ghi";
        hash[5] = "jkl";
        hash[6] = "mno";
        hash[7] = "pqrs";
        hash[8] = "tuv";
        hash[9] = "wxyz";

        path = new StringBuilder();
        ret = new ArrayList<>();

        if(digits.length() == 0) return ret;

        dfs(digits, 0);
        return ret;
    }

    void dfs(String digits, int pos) {
        if(pos == digits.length()) {
            //ret.add(String.valueOf(path));
            ret.add(path.toString());
            path.delete(pos, pos+1);
            return;
        }

        // int a = digits.charAt(pos) - '0';
        // for(int i = 0; i < hash[a].length(); i++) {
        //     path.append(hash[a].charAt(i));
        //     dfs(digits, pos + 1);//恢复现场
        //     path.delete(pos, pos + 1);
        // }
        String cur = hash[digits.charAt(pos) - '0'];
        for(int i = 0; i < cur.length(); i++) {
            path.append(cur.charAt(i));
            dfs(digits, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}